A hierarchy is a common method for organizing information. The table of contents for a book, an index system for a library and a function chart for a company's departments are examples of hierarchical arrangements of information. A hierarchy comprises nodes and their interrelationships. When a hierarchy interrelates structured nodes, those nodes are commonly called concepts (other terms used for nodes include scenes, frames, individuals and classes). The structure of a concept is described by the use of characteristics called properties.
The meaning given to these concepts and their hierarchical interrelationships depends on the real world domain that is being represented by the data hierarchy or structure. Structures comprising concepts and their interrelationships are commonly known as "part-of" decomposition hierarchies arid "is-a" abstraction hierarchies.
A "part-of" decomposition hierarchy is typically found in corporation departmental organization charts. Each sub-department is part-of a super-department. For example, the Electronic Catalog Division and Electronic Transaction Division are part-of the Electronic Commerce Division. The Electronic Commerce Division and Information Distribution Division are part-of the Internet Division which is in turn part-of the Software Division.
An "is-a" abstraction hierarchy is typically found in biological animal and organism classification charts. Each sub-abstraction is-a more specific (specialized) description of a super-abstraction. For example, the family of lions and the family of tigers are more specific descriptions of the family of large cats. The family of large cats and the family of humans are more specific descriptions of the family of mammals. The sub-concepts in these hierarchies usually share common properties with their super-concepts. We take advantage of this fact and minimize the amount of data we need to store by only defining common properties in a super-concept and allow sub-concepts of the super concept to "inherit" (access, use) these properties as part of their own definitions. Hierarchies with this characteristic are termed inheritance hierarchies. When a sub-concept can interrelate to only one super-concept, the hierarchy is termed a single inheritance concept hierarchy, and when a sub-concept can interrelate to more than one super-concept, the hierarchy is termed a multiple inheritance concept hierarchy. An example of a multiple inheritance concept hierarchy is found in the above mentioned U.S. application, Ser. No. 08/472,414, abandoned.
A way of visualizing these hierarchical data structures is by using a tree view as shown in FIG. 1. One method for visualizing any structured node in the tree view of FIG. 1, in combination with that node's properties, would be to use a concept view as shown in FIG. 2. The example given in FIG. 2 is for the "Mobile" structured concept 101 of FIG. 1.
With these two views, a user can navigate the concept hierarchy shown in FIG. 1 by starting at the root concepts "Company" or "Function" and continue thru the sub-concepts until the leaf concepts are reached. At each concept, a concept view, such as the one of FIG. 2, can be consulted for a detailed examination of the structure of the concept. Switching back and forth between hierarchial and concept type views is a popular method of investigating concept hierarchies.
The data structure shown in FIGS. 1 and 2 is created and maintained by either a human agent using a Graphic User Interface (GUI) (e.g. an information architect) or a computer agent (a software program acting on behalf of a human). A human or agent incrementally creates the data structure, representing some domain in the real world, by first adding base concepts and their property definitions. Ideally, this creation process would continue until the entire data structure is created and the whole domain is succinctly represented. In reality, however, the process of realizing a final data structure is one of continual revision and refinement. There is a continual cyclical process of creation and modification as new concepts are introduced and old ones modified.
The problem is that it is time intensive to manually recover the semantics of the hierarchy when modifying a concept's properties or interrelationships. This time expense is measured in human hours when a human is modifying the data structure and machine hours when a program is performing the modification. In both cases, the most expensive operations are those modifications done at the top of the hierarchy as it often affects all of the other sub-concepts in the hierarchy.
Modification is expensive because of the nature of hierarchical data structures with inheritance. Many of the concepts and their properties are highly interrelated and non-localized. The creation of the hierarchy is a process of building increasing complex data structures upon previously created data structures. Until now, humans and computers have had to manually reverse the creation process to effectively reset the data structure to the state it was in prior to the creation of the data structure to be modified. Often this process is so expensive and arduous that it is easier to recreate the structure than undo the creation process, make the modification and then recreate what was just undone.